1. Field of the Invention
This invention relates to digital maps of the type for displaying road information, and more particularly toward a method for updating information contained in a digital map using probe data.
2. Related Art
Personal navigation devices like that shown for example at 10 in FIG. 1 utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices have been developed for many applications, including navigation assistance for automobile drivers and delivery services. The effectiveness of any navigation system is inherently dependent upon the accuracy of the information provided to it in the form of digital maps, stored in its memory or otherwise accessed through a suitable database connection such as wireless signal, cable, telephone line, etc.
Typically, a navigation system 10 includes a display screen 12 that portrays a portion of a stored digital map as a network of roads 14. A navigation system 10 can be a dedicated portable device like shown in FIG. 1, a personal computer, cellular phone, smart phone, personal digital assistant, or other device. The navigation system 10 may or may not be GPS-enabled. A traveler having access to a GPS-enabled navigation device 10 may then be generally located on the digital map close to or with regard to a particular road 14 or segment thereof.
Some GPS-enabled navigation devices 10, like several models manufactured by TomTom NV (www.tomtom.com), may also be configured as probes to passively generate probe measurement points at regular intervals. Such probe measurements from a single device are strung together as traces, which comprise a sequence of discrete geo-coded positions recorded at intervals of, for example, five seconds. A single trace represents a journey of a single vehicle from or near a starting point to a destination point. Of course, other suitable devices may be used to generate probe measurement points including, for example, handheld devices, mobile phones, PDAs, and the like. Thus, probe data may be described as a set of information about the movements of a vehicle (or a person carrying a probe) which contains time-stamped geographic locations (xyz coordinates) and possibly also metadata (vehicle speed, receiver type, vehicle type, etc.).
It is known to take collections of probe measurements from multiple traces and vehicles for the purpose of incrementally creating and/or updating digital maps. The probe measurements can be transmitted either on-the-fly or subsequently to a collection service or other map data analysis service via wireless (e.g., cellular) transmission, via Internet uploads, or by other convenient methods. Internet uploads may be synchronized to occur in conjunction with digital map upgrades which navigation device users might obtain as part of a service. From the collection of probe measurements, road geometries can be inferred and other features and attributes derived by appropriate analytical methods.
Digital maps are frequently composed as a mosaic of geo-coded image tiles which, when arranged side by side, create a bird's eye mosaic (BEM) of a particular surface of interest, such as a section of land on the earth. An exemplary tile is generally indicated at 16 in FIG. 2 and may represent either a non-rectified or an orthorectified area of land. The particular size or scale of a tile 16 can vary from one digital map to the next, but as shown in FIG. 2, frequently comprises an area sufficient to contain a modest number of roads 14 and road segments. Thus, the tile 16 shown in FIG. 2 would be merely one of many tiles stitched together to make up a digital map of the type contained in a digital map database.
Probe traces collected over time can be grouped according to those which match to a common tile 16 and then overlaid for interpretation by database editors. Editors use various mathematic and statistical techniques to determine or infer road geometries, compute speed profiles, acceleration profiles, direction of travel, altitude, detect changes in road networks, to compare two road networks, and the like. A typical collection of probe measurements collected from a plurality of probes traversing a particular tile section over an extended period of time may contain billions of discrete data points, each time stamped. See, for example, FIG. 3 which represents the tile 16 of FIG. 2 overlaid with exemplary probe data. Each probe trace comprises a sequence of data points generated by a single device, typically carried in a motor vehicle as it travels over the road network in real life. As mentioned above, the data points generated by the complete start to stop journey of a single vehicle can be referred to as a “trip.”
As suggested previously, the effectiveness of a personal navigation device 10 depends upon the accuracy of the information contained in the digital map. Digital map providers continuously strive to improve and update their maps. Inaccurate or incomplete data, for example, may be unsuitable to compute optimal routes in response to a navigation query, or to otherwise provide unreliable information to a traveler. Frequently, navigation decisions will take into account suitable parking accommodations for a motor vehicle. For example, in dense, urban areas, parking lots or car parks may be rather scarce and difficult to find. The precise location of car parks is an important detail to be recorded in a digital map, however these features have been largely determined using historic information which may not reflect a present reality. Furthermore, the location and size of car parks frequently changes in response to periodic construction and maintenance activities, and therefore the need to provide up-to-date information regarding the location of parking lots is highly relevant.
Until now, there is no effective method by which to analyze probe measurements to determine the location, size, classification or other relevant details of a parking lot. In part, privacy concerns about the movement of vehicles that produce probe traces have resulted in a custom whereby the beginning and end of each probe trace is truncated. Unfortunately, these beginning and/or end points are most pertinent relative to car parking locations. Therefore, there is a need in the art for an improved method for effectively analyzing probe data that may have been truncated for privacy reasons to validate and/or determine specifications for car parking facilities relative to a road network in a digital map.